Crate winter_fri

Expand description

This crate contains an implementation of the FRI protocol used by the Winterfell STARK prover and verifier.

FRI stands for Fast Reed-Solomon Interactive Oracle Proof of Proximity, and is used in the STARK protocol for low-degree testing. Specifically, given a commitment to a set of evaluations of some function over domain D, the verifier can be convinced that the function is a polynomial of degree at most d, by making a small number of queries to the commitment.

Proof generation

FRI proofs are generated by a FriProver in two steps:

First, the commit phase of the protocol is executed via build_layers() function. During this phase, the degree of the polynomial is repeatedly reduced by applying a degree-respecting projection, until the size of the domain over which the polynomial is evaluated falls under max_remainder_size parameter. While performing the reduction, the prover writes a set of layer commitments into the ProverChannel. These commitments should be recorded and sent to the verifier as they will be needed during the proof verification procedure.
Then, the query phase of the protocol is executed via build_proof() function. The output of this function is an instance of the FriProof struct. When FRI is executed as a part of the STARK protocol, FRI proof is included into a STARK proof.

When the crate is compiled with concurrent feature enabled, proof generation will be performed in multiple threads (usually, as many threads as there are logical cores on the machine). The number of threads can be configured via RAYON_NUM_THREADS environment variable.

Proof verification

FRI proofs are verified by a FriVerifier as follows:

First, a FRI proof needs to be converted into a VerifierChannel. This crate provides a default implementation of the verifier channel, but when FRI proof verification is executed as a part of the larger STARK protocol, STARK verifier handles this conversion.
Then, a FriVerifier should be instantiated (via new() function). This will execute the commit phase of the FRI protocol from the verifier’s perspective - i.e., the verifier will read FRI layer commitments from the channel, and generates random values needed for layer folding.
Finally, the query phase of the FRI protocol should be executed via verify() function. Note that query values at the first FRI layer are provided to the verify() function directly. The values at remaining layers, the verifier reads from the specified verifier channel.